package sit.engreal.leetcode.problems100;

import org.junit.jupiter.api.Assertions;

/**
 * <a href="https://leetcode.cn/problems/valid-parentheses/"> 20. 有效的括号 </a>
 */
public class LeetCode20 {
    static class Solution {
        public boolean isValid(String s) {
            char[] stack = new char[s.length() + 1];
            stack[0] = '#';
            int top = 0;

            for (int i = 0; i < s.length(); i++) {
                final char c = s.charAt(i);
                if ('(' == c || '[' == c || '{' == c) {
                    top++;
                    stack[top] = c;
                } else if ((')' == c && '(' == stack[top])
                        || (']' == c && '[' == stack[top])
                        || ('}' == c && '{' == stack[top])) {
                    top--;
                } else {
                    return false;
                }
            }

            return '#' == stack[top];
        }
    }

    public static void main(String[] args) {
        final Solution solution = new Solution();

        Assertions.assertTrue(solution.isValid("()"));
        Assertions.assertTrue(solution.isValid("()[]{}"));

        Assertions.assertFalse(solution.isValid("(]"));
        Assertions.assertFalse(solution.isValid("]"));
        Assertions.assertFalse(solution.isValid("["));
    }
}
